//算法5.1 中序遍历的递归算法
#include<stdio.h>
#include<stdlib.h>
typedef struct BiNode{				//二叉链表定义
	char data;
	struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;

//用算法5.3 先序遍历的顺序建立二叉链表
BiTree CreateBiTree(){	
	//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	//scanf("%c",&ch);
	ch=getchar();
	getchar();//获取多余的回车键，清空缓冲区
	BiTree T=NULL;
	if(ch!='#'){		
		T=(BiTNode*)malloc(sizeof(BiTNode));
		T->data=ch;//生成根结点
		T->lchild=CreateBiTree();//递归创建左子树
		T->rchild=CreateBiTree();//递归创建右子树		
	}//else
	return T;
}//CreateBiTree

void InOrderTraverse(BiTNode *T){  
	//中序遍历二叉树T的递归算法
	if(T){
		InOrderTraverse(T->lchild);
		printf("%c",T->data);
		InOrderTraverse(T->rchild);
	}
}

void preOrderTraverse(BiTNode *T){  
	//中序遍历二叉树T的递归算法
	if(T){
		printf("%c",T->data);
		preOrderTraverse(T->lchild);		
		preOrderTraverse(T->rchild);
	}
}

void postOrderTraverse(BiTNode *T){  
	//中序遍历二叉树T的递归算法
	if(T){
		postOrderTraverse(T->lchild);		
		postOrderTraverse(T->rchild);
		printf("%c",T->data);
	}
}

int main(){
	BiTree tree=NULL;
	printf("请输入建立二叉链表的序列：\n");
	tree=CreateBiTree();
	printf("先序遍历的结果为：\n");
	preOrderTraverse(tree);
	printf("\n");
	printf("中序遍历的结果为：\n");
	InOrderTraverse(tree);
	printf("\n");
	printf("后序遍历的结果为：\n");
	postOrderTraverse(tree);
	printf("\n");
	return 0;
}
